package com.xjl.sort;

import com.xjl.utils.SortUtil;

import javax.xml.transform.Source;
import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @描述： 堆排序
 *         解决两个问题： ① 如何将 N 个元素的无序序列建成一个堆
 *                       ② 输出堆元素后，怎样调节剩下的元素，使其成为一个新堆
 * @作者： 许JIAN林
 */
public class HeapSort {

    /**
     * 堆排序
     * @param arr
     */
    public static  void HeapSort(int[] arr) {
        if (arr == null || arr.length < 2 ){
            return;
        }
        for (int i = 0; i<arr.length; i++) {
            CreatHeap(arr, i);
        }
        int heapsize = arr.length;
        SortUtil.swap(arr, 0, --heapsize);
        while( heapsize >0) {
            InitHeap(arr, 0, heapsize);
            SortUtil.swap(arr, 0, --heapsize);

        }
    }

    /**
     * 构建大根堆
     * @param arr
     * @param index
     */
    public static void CreatHeap( int[] arr, int index) {
        while( arr[index] > arr[ (index - 1) / 2]) {
            SortUtil.swap(arr, index, (index -1) /2 );
            index = (index - 1) /2 ;
        }
    }

    /**
     * 重新初始化大根堆
     * @param arr
     * @param index
     * @param heapsize
     */
    public static void InitHeap(int[] arr, int index, int heapsize) {
        int left = index * 2  + 1;
        while (left < heapsize) {
            int bigest =  left + 1 < heapsize && arr[left + 1] > arr[left]
                    ? left + 1
                    : left ;
            bigest = arr[bigest] > arr[index] ? bigest : index ;
            if (bigest == index) {
                break;
            }
            SortUtil.swap(arr, bigest, index);
            index = bigest;
            left = index * 2 + 1 ;
        }

    }


    public static void main(String[] args) {

//        int[] getarr = new int[]{6, 4, 1, 5, 3, 1, 3};

        int[] getarr = SortUtil.getarr(7, 10);

//        Arrays.sort(getarr);  //系统函数
        HeapSort(getarr);
        System.out.println("堆排序数组");
        SortUtil.display(getarr);

    }
}
